emscripten
Downloading...

Resize canvas Lock/hide mouse pointer    


/ >> augmented_containers >> augmented_deque_t
jhcarl0814.github.io
	Augmented Containers
		Sequence
			augmented_*****_t
			augmented_********_t
		Associative
			augmented_***​/​***​/​********​/​********_t
		*****
			augmented_*****_t

augmented_containers::augmented_deque_t

#include<augmented_containers/augmented_deque.hpp> (one single header file library)
template<
	typename element_t,
	typename allocator_t = std::allocator<element_t>,
	typename requested_stride_to_projector_and_accumulator_map_t = std::tuple<>
> struct augmented_deque_t;

augmented_deque_t is an augmented, strictly double-ended queue. It's part of the augmented containers library, providing a stronger version of sequence containers (let containers (and possibly its subranges) always have several accompanying results of algorithms/views), as well as <algorithm> and <ranges> (when the input sequence changes, refresh output values/ranges in logarithmic time complexity).

Complexity Table

possible implementations
adding a side deque augmented balanced tree augmented_deque_t
operations range update O(N), O(distance(range)) if range's begin/end is at accumulation end O(distance(range)+lg(N)) O(distance(range)+lg(N))
subrange query O(distance(range)), O(1) if range's begin/end is at accumulation begin O(lg(distance(range))) O(lg(distance(range)))
enqueue O(1) O(lg(N)) O(1)
dequeue O(1) O(lg(N)) O(1)
modify element at either end, then update O(N), O(1) if at the accumulation end O(lg(N)) O(1)

How to achieve O(1) enqueue && O(1) dequeue && O(lg(N)) accumulation depth?

augmented_deque_t is a node-based container. First the element nodes forms a doubly linked list, then tree nodes organize them into prefect binary trees. The enqueue and dequeue operations are analogous to operator++ and operator-- in binary positional numeral system.

test_graphcluster_base3base3cluster_base2_low_passbase2_low_passcluster_base2base2base3_00000000base3_00010001base3_00020002base3_00100010base3_00110011base3_00120012base3_00200020base3_00210021base3_00220022base3_01000100base3_01010101base3_01020102base3_01100110base3_01110111base3_01120112base3_01200120base3_01210121base3_01220122base3_02000200base3_02010201base3_02020202base3_02100210base3_02110211base3_02120212base3_02200220base3_02210221base3_02220222base3_10001000base3_10011001base3_10021002base3_10101010base3_10111011base3_10121012base3_10201020base3_10211021base3_10221022base3_11001100base3_11011101base3_11021102base3_11101110base3_11111111base3_11121112base3_11201120base3_11211121base3_11221122base3_12001200base3_12011201base3_12021202base3_12101210base3_12111211base3_12121212base3_12201220base3_12211221base3_12221222base3_20002000base3_20012001base3_20022002base3_20102010base3_20112011base3_20122012base3_20202020base3_20212021base3_20222022base3_21002100base3_21012101base3_21022102base3_21102110base3_21112111base3_21122112base3_21202120base3_21212121base3_21222122base3_22002200base3_22012201base3_22022202base3_22102210base3_22112211base3_22122212base3_22202220base3_22212221base3_22222222base2_low_pass_00000000base2_low_pass_00010001base2_low_pass_00020002base2_low_pass_00110011base2_low_pass_00100010base2_low_pass_00120012base2_low_pass_00210021base2_low_pass_00200020base2_low_pass_00220022base2_low_pass_01110111base2_low_pass_01000100base2_low_pass_01010101base2_low_pass_01020102base2_low_pass_01100110base2_low_pass_01120112base2_low_pass_01210121base2_low_pass_01200120base2_low_pass_01220122base2_low_pass_02110211base2_low_pass_02000200base2_low_pass_02010201base2_low_pass_02020202base2_low_pass_02100210base2_low_pass_02120212base2_low_pass_02210221base2_low_pass_02200220base2_low_pass_02220222base2_low_pass_11111111base2_low_pass_10001000base2_low_pass_10011001base2_low_pass_10021002base2_low_pass_10111011base2_low_pass_10101010base2_low_pass_10121012base2_low_pass_10211021base2_low_pass_10201020base2_low_pass_10221022base2_low_pass_11001100base2_low_pass_11011101base2_low_pass_11021102base2_low_pass_11101110base2_low_pass_11121112base2_low_pass_11211121base2_low_pass_11201120base2_low_pass_11221122base2_low_pass_12111211base2_low_pass_12001200base2_low_pass_12011201base2_low_pass_12021202base2_low_pass_12101210base2_low_pass_12121212base2_low_pass_12211221base2_low_pass_12201220base2_low_pass_12221222base2_low_pass_21112111base2_low_pass_20002000base2_low_pass_20012001base2_low_pass_20022002base2_low_pass_20112011base2_low_pass_20102010base2_low_pass_20122012base2_low_pass_20212021base2_low_pass_20202020base2_low_pass_20222022base2_low_pass_21002100base2_low_pass_21012101base2_low_pass_21022102base2_low_pass_21102110base2_low_pass_21122112base2_low_pass_21212121base2_low_pass_21202120base2_low_pass_21222122base2_low_pass_22112211base2_low_pass_22002200base2_low_pass_22012201base2_low_pass_22022202base2_low_pass_22102210base2_low_pass_22122212base2_low_pass_22212221base2_low_pass_22202220base2_low_pass_22222222base2_00000000base2_00010001base2_00100010base2_00110011base2_01000100base2_01010101base2_01100110base2_01110111base2_10001000base2_10011001base2_10101010base2_10111011base2_11001100base2_11011101base2_11101110base2_11111111base3_0000->base3_0001base3_0001->base3_0000base3_0001->base3_0002base3_0002->base3_0001base3_0002->base3_0010base3_0010->base3_0002base3_0010->base3_0011base3_0011->base3_0010base3_0011->base3_0012base3_0012->base3_0011base3_0012->base3_0020base3_0020->base3_0012base3_0020->base3_0021base3_0021->base3_0020base3_0021->base3_0022base3_0022->base3_0021base3_0022->base3_0100base3_0100->base3_0022base3_0100->base3_0101base3_0101->base3_0100base3_0101->base3_0102base3_0102->base3_0101base3_0102->base3_0110base3_0110->base3_0102base3_0110->base3_0111base3_0111->base3_0110base3_0111->base3_0112base3_0112->base3_0111base3_0112->base3_0120base3_0120->base3_0112base3_0120->base3_0121base3_0121->base3_0120base3_0121->base3_0122base3_0122->base3_0121base3_0122->base3_0200base3_0200->base3_0122base3_0200->base3_0201base3_0201->base3_0200base3_0201->base3_0202base3_0202->base3_0201base3_0202->base3_0210base3_0210->base3_0202base3_0210->base3_0211base3_0211->base3_0210base3_0211->base3_0212base3_0212->base3_0211base3_0212->base3_0220base3_0220->base3_0212base3_0220->base3_0221base3_0221->base3_0220base3_0221->base3_0222base3_0222->base3_0221base3_0222->base3_1000base3_1000->base3_0222base3_1000->base3_1001base3_1001->base3_1000base3_1001->base3_1002base3_1002->base3_1001base3_1002->base3_1010base3_1010->base3_1002base3_1010->base3_1011base3_1011->base3_1010base3_1011->base3_1012base3_1012->base3_1011base3_1012->base3_1020base3_1020->base3_1012base3_1020->base3_1021base3_1021->base3_1020base3_1021->base3_1022base3_1022->base3_1021base3_1022->base3_1100base3_1100->base3_1022base3_1100->base3_1101base3_1101->base3_1100base3_1101->base3_1102base3_1102->base3_1101base3_1102->base3_1110base3_1110->base3_1102base3_1110->base3_1111base3_1111->base3_1110base3_1111->base3_1112base3_1112->base3_1111base3_1112->base3_1120base3_1120->base3_1112base3_1120->base3_1121base3_1121->base3_1120base3_1121->base3_1122base3_1122->base3_1121base3_1122->base3_1200base3_1200->base3_1122base3_1200->base3_1201base3_1201->base3_1200base3_1201->base3_1202base3_1202->base3_1201base3_1202->base3_1210base3_1210->base3_1202base3_1210->base3_1211base3_1211->base3_1210base3_1211->base3_1212base3_1212->base3_1211base3_1212->base3_1220base3_1220->base3_1212base3_1220->base3_1221base3_1221->base3_1220base3_1221->base3_1222base3_1222->base3_1221base3_1222->base3_2000base3_2000->base3_1222base3_2000->base3_2001base3_2001->base3_2000base3_2001->base3_2002base3_2002->base3_2001base3_2002->base3_2010base3_2010->base3_2002base3_2010->base3_2011base3_2011->base3_2010base3_2011->base3_2012base3_2012->base3_2011base3_2012->base3_2020base3_2020->base3_2012base3_2020->base3_2021base3_2021->base3_2020base3_2021->base3_2022base3_2022->base3_2021base3_2022->base3_2100base3_2100->base3_2022base3_2100->base3_2101base3_2101->base3_2100base3_2101->base3_2102base3_2102->base3_2101base3_2102->base3_2110base3_2110->base3_2102base3_2110->base3_2111base3_2111->base3_2110base3_2111->base3_2112base3_2112->base3_2111base3_2112->base3_2120base3_2120->base3_2112base3_2120->base3_2121base3_2121->base3_2120base3_2121->base3_2122base3_2122->base3_2121base3_2122->base3_2200base3_2200->base3_2122base3_2200->base3_2201base3_2201->base3_2200base3_2201->base3_2202base3_2202->base3_2201base3_2202->base3_2210base3_2210->base3_2202base3_2210->base3_2211base3_2211->base3_2210base3_2211->base3_2212base3_2212->base3_2211base3_2212->base3_2220base3_2220->base3_2212base3_2220->base3_2221base3_2221->base3_2220base3_2221->base3_2222base3_2222->base3_2221base2_low_pass_0000->base2_low_pass_0001base2_low_pass_0001->base2_low_pass_0000base2_low_pass_0001->base2_low_pass_0002base2_low_pass_0002->base2_low_pass_0001base2_low_pass_0002->base2_low_pass_0011base2_low_pass_0011->base2_low_pass_0010base2_low_pass_0011->base2_low_pass_0012base2_low_pass_0010->base2_low_pass_0001base2_low_pass_0010->base2_low_pass_0011base2_low_pass_0012->base2_low_pass_0011base2_low_pass_0012->base2_low_pass_0021base2_low_pass_0021->base2_low_pass_0020base2_low_pass_0021->base2_low_pass_0022base2_low_pass_0020->base2_low_pass_0011base2_low_pass_0020->base2_low_pass_0021base2_low_pass_0022->base2_low_pass_0021base2_low_pass_0022->base2_low_pass_0111base2_low_pass_0111->base2_low_pass_0110base2_low_pass_0111->base2_low_pass_0112base2_low_pass_0100->base2_low_pass_0011base2_low_pass_0100->base2_low_pass_0101base2_low_pass_0101->base2_low_pass_0100base2_low_pass_0101->base2_low_pass_0102base2_low_pass_0102->base2_low_pass_0111base2_low_pass_0102->base2_low_pass_0101base2_low_pass_0110->base2_low_pass_0111base2_low_pass_0110->base2_low_pass_0101base2_low_pass_0112->base2_low_pass_0111base2_low_pass_0112->base2_low_pass_0121base2_low_pass_0121->base2_low_pass_0120base2_low_pass_0121->base2_low_pass_0122base2_low_pass_0120->base2_low_pass_0111base2_low_pass_0120->base2_low_pass_0121base2_low_pass_0122->base2_low_pass_0121base2_low_pass_0122->base2_low_pass_0211base2_low_pass_0211->base2_low_pass_0210base2_low_pass_0211->base2_low_pass_0212base2_low_pass_0200->base2_low_pass_0111base2_low_pass_0200->base2_low_pass_0201base2_low_pass_0201->base2_low_pass_0200base2_low_pass_0201->base2_low_pass_0202base2_low_pass_0202->base2_low_pass_0211base2_low_pass_0202->base2_low_pass_0201base2_low_pass_0210->base2_low_pass_0211base2_low_pass_0210->base2_low_pass_0201base2_low_pass_0212->base2_low_pass_0211base2_low_pass_0212->base2_low_pass_0221base2_low_pass_0221->base2_low_pass_0220base2_low_pass_0221->base2_low_pass_0222base2_low_pass_0220->base2_low_pass_0211base2_low_pass_0220->base2_low_pass_0221base2_low_pass_0222->base2_low_pass_0221base2_low_pass_0222->base2_low_pass_1111base2_low_pass_1111->base2_low_pass_1110base2_low_pass_1111->base2_low_pass_1112base2_low_pass_1000->base2_low_pass_0111base2_low_pass_1000->base2_low_pass_1001base2_low_pass_1001->base2_low_pass_1000base2_low_pass_1001->base2_low_pass_1002base2_low_pass_1002->base2_low_pass_1001base2_low_pass_1002->base2_low_pass_1011base2_low_pass_1011->base2_low_pass_1010base2_low_pass_1011->base2_low_pass_1012base2_low_pass_1010->base2_low_pass_1001base2_low_pass_1010->base2_low_pass_1011base2_low_pass_1012->base2_low_pass_1011base2_low_pass_1012->base2_low_pass_1021base2_low_pass_1021->base2_low_pass_1020base2_low_pass_1021->base2_low_pass_1022base2_low_pass_1020->base2_low_pass_1011base2_low_pass_1020->base2_low_pass_1021base2_low_pass_1022->base2_low_pass_1111base2_low_pass_1022->base2_low_pass_1021base2_low_pass_1100->base2_low_pass_1011base2_low_pass_1100->base2_low_pass_1101base2_low_pass_1101->base2_low_pass_1100base2_low_pass_1101->base2_low_pass_1102base2_low_pass_1102->base2_low_pass_1111base2_low_pass_1102->base2_low_pass_1101base2_low_pass_1110->base2_low_pass_1111base2_low_pass_1110->base2_low_pass_1101base2_low_pass_1112->base2_low_pass_1111base2_low_pass_1112->base2_low_pass_1121base2_low_pass_1121->base2_low_pass_1120base2_low_pass_1121->base2_low_pass_1122base2_low_pass_1120->base2_low_pass_1111base2_low_pass_1120->base2_low_pass_1121base2_low_pass_1122->base2_low_pass_1121base2_low_pass_1122->base2_low_pass_1211base2_low_pass_1211->base2_low_pass_1210base2_low_pass_1211->base2_low_pass_1212base2_low_pass_1200->base2_low_pass_1111base2_low_pass_1200->base2_low_pass_1201base2_low_pass_1201->base2_low_pass_1200base2_low_pass_1201->base2_low_pass_1202base2_low_pass_1202->base2_low_pass_1211base2_low_pass_1202->base2_low_pass_1201base2_low_pass_1210->base2_low_pass_1211base2_low_pass_1210->base2_low_pass_1201base2_low_pass_1212->base2_low_pass_1211base2_low_pass_1212->base2_low_pass_1221base2_low_pass_1221->base2_low_pass_1220base2_low_pass_1221->base2_low_pass_1222base2_low_pass_1220->base2_low_pass_1211base2_low_pass_1220->base2_low_pass_1221base2_low_pass_1222->base2_low_pass_1221base2_low_pass_1222->base2_low_pass_2111base2_low_pass_2111->base2_low_pass_2110base2_low_pass_2111->base2_low_pass_2112base2_low_pass_2000->base2_low_pass_1111base2_low_pass_2000->base2_low_pass_2001base2_low_pass_2001->base2_low_pass_2000base2_low_pass_2001->base2_low_pass_2002base2_low_pass_2002->base2_low_pass_2001base2_low_pass_2002->base2_low_pass_2011base2_low_pass_2011->base2_low_pass_2010base2_low_pass_2011->base2_low_pass_2012base2_low_pass_2010->base2_low_pass_2001base2_low_pass_2010->base2_low_pass_2011base2_low_pass_2012->base2_low_pass_2011base2_low_pass_2012->base2_low_pass_2021base2_low_pass_2021->base2_low_pass_2020base2_low_pass_2021->base2_low_pass_2022base2_low_pass_2020->base2_low_pass_2011base2_low_pass_2020->base2_low_pass_2021base2_low_pass_2022->base2_low_pass_2111base2_low_pass_2022->base2_low_pass_2021base2_low_pass_2100->base2_low_pass_2011base2_low_pass_2100->base2_low_pass_2101base2_low_pass_2101->base2_low_pass_2100base2_low_pass_2101->base2_low_pass_2102base2_low_pass_2102->base2_low_pass_2111base2_low_pass_2102->base2_low_pass_2101base2_low_pass_2110->base2_low_pass_2111base2_low_pass_2110->base2_low_pass_2101base2_low_pass_2112->base2_low_pass_2111base2_low_pass_2112->base2_low_pass_2121base2_low_pass_2121->base2_low_pass_2120base2_low_pass_2121->base2_low_pass_2122base2_low_pass_2120->base2_low_pass_2111base2_low_pass_2120->base2_low_pass_2121base2_low_pass_2122->base2_low_pass_2121base2_low_pass_2122->base2_low_pass_2211base2_low_pass_2211->base2_low_pass_2210base2_low_pass_2211->base2_low_pass_2212base2_low_pass_2200->base2_low_pass_2111base2_low_pass_2200->base2_low_pass_2201base2_low_pass_2201->base2_low_pass_2200base2_low_pass_2201->base2_low_pass_2202base2_low_pass_2202->base2_low_pass_2211base2_low_pass_2202->base2_low_pass_2201base2_low_pass_2210->base2_low_pass_2211base2_low_pass_2210->base2_low_pass_2201base2_low_pass_2212->base2_low_pass_2211base2_low_pass_2212->base2_low_pass_2221base2_low_pass_2221->base2_low_pass_2220base2_low_pass_2221->base2_low_pass_2222base2_low_pass_2220->base2_low_pass_2211base2_low_pass_2220->base2_low_pass_2221base2_low_pass_2222->base2_low_pass_2221base2_0000->base2_0001base2_0001->base2_0000base2_0001->base2_0010base2_0010->base2_0001base2_0010->base2_0011base2_0011->base2_0010base2_0011->base2_0100base2_0100->base2_0011base2_0100->base2_0101base2_0101->base2_0100base2_0101->base2_0110base2_0110->base2_0101base2_0110->base2_0111base2_0111->base2_0110base2_0111->base2_1000base2_1000->base2_0111base2_1000->base2_1001base2_1001->base2_1000base2_1001->base2_1010base2_1010->base2_1001base2_1010->base2_1011base2_1011->base2_1010base2_1011->base2_1100base2_1100->base2_1011base2_1100->base2_1101base2_1101->base2_1100base2_1101->base2_1110base2_1110->base2_1101base2_1110->base2_1111base2_1111->base2_1110

... and note that in the implementation it's double ended (the most significant bit is in the middle and shared by the front part and the back part). The accumulation direction is from the middle digit to both ends (the accumulator should be able to accumulate up to 3 (instead of 2) values at a time, e.g. for each digit node on the right, calculate sum of values from its prev digit node, from its left tree root and from its right tree root), then accumulate the ends together yielding the overall accumulated result of the whole container. That's why updating a element at (near) either end and refreshing the accumulated results only takes O(1).

Examples

The untagged pointers are drawn as solid lines. The 0b1-tagged pointers are drawn as dashed lines.

In each sub-sequence, the digit nodes are organized into a circular doubly linked list. Pointers from/to the end node are 0b1-tagged. The end node's next, middle, prev and accumulated_storage are drawn separately to not break graphviz's layout.

In each digit node's each tree, the tree nodes are organized into a perfect binary tree. The pointer from the root tree node to digit node and pointers from leaf tree nodes to list nodes are 0b1-tagged.

In each sub-sequence, the list nodes are organized into a circular doubly linked list. Pointers from/to the end node are 0b1-tagged. The end node is not drawn to not break graphviz's layout.

empty

The projection and accumulation steps are skipped. What's left can be seen as a std::vector/std::deque that never invalidates iterators/references/pointers, or a std::list with random access ability.

augmented_containers::augmented_deque_t<
	char,
	std::allocator<char>
> augmented_deque;

accumulator_only_yield_one_value_string

The projection step is skipped. element_t(char)s are accumulated into accumulated_storage_t(std::string)s.

augmented_containers::augmented_deque_t<
	char,
	std::allocator<char>,
	std::tuple<
		std::pair<std::integral_constant<std::size_t, 1>, augmented_containers::augmented_deque_helpers::example_stride1_chunk1_projector_skipped_and_accumulator_sequence_t<char, std::string>>
	>
>

projector_and_accumulator_yield_one_value_int

augmented_containers::augmented_deque_t<
	int,
	std::allocator<int>,
	std::tuple<
		std::pair<std::integral_constant<std::size_t, 1>, augmented_containers::augmented_deque_helpers::example_stride1_chunk1_projector_skipped_and_accumulator_plus_t<int>>,
		std::pair<std::integral_constant<std::size_t, 3>, augmented_containers::augmented_deque_helpers::example_chunkgt1_projector_max_element_and_accumulator_min_t<int>>
	>
> augmented_deque;

projector_and_accumulator_yield_one_value_string

augmented_containers::augmented_deque_t<
	std::string,
	std::allocator<std::string>,
	std::tuple<
		std::pair<std::integral_constant<std::size_t, 1>, augmented_containers::augmented_deque_helpers::example_stride1_chunk1_projector_skipped_and_accumulator_plus_t<std::string>>,
		std::pair<std::integral_constant<std::size_t, 3>, augmented_containers::augmented_deque_helpers::example_chunkgt1_projector_max_element_and_accumulator_min_t<std::string>>
	>
> augmented_deque;

projector_and_accumulator_yield_multiple_values

augmented_containers::augmented_deque_t<
	int,
	std::allocator<int>,
	std::tuple<
		//std::pair<std::integral_constant<std::size_t, 3>, projector_and_accumulator_min_n_element_t<int, 3>>, //commented one of the sub-sequences because it looks messy when there are three images stacked together
		std::pair<std::integral_constant<std::size_t, 3>, projector_and_accumulator_min_n_element_t<int, 3, true>>
	>
> augmented_deque;

projector_and_accumulator_yield_one_view

Each element_t(int) is projected into the navigator portion (prev and next pointers) to be ready to form a circular doubly linked list. The accumulator takes chunk-begins (std::ranges::prev(it).is_end() || (*std::ranges::prev(it) < 50) != (*it < 50)), discards non-chunk-begins (and takes other accumulated circular doubly linked lists), accumulates them into a circular doubly linked lists representing std::ranges::chunk_by_view of the original sequence.

augmented_containers::augmented_deque_t<
	int,
	std::allocator<int>,
	std::tuple<
		std::pair<std::integral_constant<std::size_t, 1>, projector_and_accumulator_diffing_adjacent_element_t>
	>
> augmented_deque;

projector_and_accumulator_yield_multiple_views

Similar to the projector_and_accumulator_yield_one_view example, except that each accumulated_storage_t is "a map from element % 3 to circular doubly linked list's end node" (instead of just "one end node"). The result represents C++32's std::ranges::group_by_view of the original sequence (navigator_style = std::ranges::group_by_view::navigator_style_t::circular_doubly_linked_list, map_container_tt = std::map).

augmented_containers::augmented_deque_t<
	int,
	std::allocator<int>,
	std::tuple<
		std::pair<std::integral_constant<std::size_t, 1>, projector_and_accumulator_group_by_t>
	>
> augmented_deque;

find_by_monotonic_predicate

Each element_t(std::string) is projected into its .size(); accumulator is std::size_t operator+(std::size_t, std::size_t). Use .find_by_monotonic_predicate([&](){ ... }) to find the first element where the accumulated_storage_t(std::size_t) (accumulated string size so far) starts to be greater than the given character index, i.e., the element that contains the the given character indexth character. Note that the hierarchical structure saves time by skiping substructures that don't contain the results.

augmented_containers::augmented_deque_t<
    std::string,
    std::allocator<std::string>,
    std::tuple<
        std::pair<std::integral_constant<std::size_t, 1>, augmented_containers::augmented_deque_helpers::projector_and_accumulator_wrapping_projecting_and_accumulating_functors_t<projecting_n_ary_functor_string_to_length_t, augmented_containers::augmented_deque_helpers::accumulating_binary_functor_wrapping_homogeneous_binary_functor_t<std::size_t, std::plus<std::size_t>>>>
	>
> augmented_deque;

find_by_heap_predicate

The projection step is skipped. element_t(int)s are accumulated into their std::ranges::max. Use .find_by_heap_predicate(itps_output, [&](){ ... }) to eagerly find all elements greater than or equal to the given threshold. Note that the hierarchical structure saves time by skiping substructures that don't contain the results. It's possible to parallelize the search, depending on the availability of std::execution.

augmented_containers::augmented_deque_t<
    int,
    std::allocator<int>,
    std::tuple<
        std::pair<std::integral_constant<std::size_t, 1>, augmented_containers::augmented_deque_helpers::projector_and_accumulator_wrapping_projecting_and_accumulating_functors_t<void, augmented_containers::augmented_deque_helpers::accumulating_binary_functor_wrapping_homogeneous_binary_functor_t<int, augmented_containers::augmented_deque_helpers::max_t<int>>>>
	>
> augmented_deque;

find_by_heap_predicate_generator

Each element_t(std::pair<std::int64_t, std::int64_t>) is projected into its .second (upper endpoint), then accumulated into their std::ranges::max. Use .find_by_heap_predicate_generator([&](){ ... }) to lazily iterate through elements whose upper endpoints are greater than or equal to the given interval's lower endpoint, until lower endpoint is greater than the given interval's upper endpoint, i.e., the elements that intersect with the given interval. Note that the hierarchical structure saves time by skiping substructures that don't contain the results. It's possible to parallelize the search, depending on the availability of std::execution.

augmented_containers::augmented_deque_t<
    std::pair<std::int64_t, std::int64_t>,
    std::allocator<std::pair<std::int64_t, std::int64_t>>,
    std::tuple<
        std::pair<std::integral_constant<std::size_t, 1>, augmented_containers::augmented_deque_helpers::projector_and_accumulator_wrapping_projecting_and_accumulating_functors_t<projecting_n_ary_functor_interval_to_upper_endpoint_t, augmented_containers::augmented_deque_helpers::accumulating_binary_functor_wrapping_homogeneous_binary_functor_t<int, augmented_containers::augmented_deque_helpers::max_t<std::int64_t>>>>
	>
> augmented_deque;

Relationship with <algorithm> and <ranges>

The table shows the constructs that augmented_deque_t provides a stronger replacement of and the constructs that are not relevant and the reasons.

headers
<algorithm> <ranges>
how to handle use projection to handle (without accumulation) transform adjacent_difference ranges::transform_view ranges::elements_view ranges::keys_view ranges::values_view ranges::adjacent_view ranges::adjacent_transform_view ranges::slide_view ranges::chunk_view ranges::stride_view
use accumulation (possibly after projection) to handle all_of, any_of, none_of count count_if find find_first_of adjacent_find is_partitioned partition_point is_sorted is_sorted_until max_element min_element minmax_element accumulate (reduce, transform_reduce) ranges::join_view ranges::join_with_view
use accumulation (possibly after projection) + read_range to handle partial_sum exclusive_scan (transform_exclusive_scan) inclusive_scan (transform_inclusive_scan)
use yield_multiple_values example to handle nth_element (when n is small) make_heap push_heap pop_heap sort_heap
use yield_one_view example to handle lower_bound (yields one view of iterators, distance > 1 when original sequence is not sorted) upper_bound (yields one view of iterators, distance > 1 when original sequence not sorted) equal_ranges (yields one view of ranges, distance > 1 when original sequence not sorted) ranges::filter_view ranges::take_view ranges::take_while_view ranges::drop_view ranges::drop_while_view ranges::split_view ranges::chunk_by_view
not relevant for_each generate iota ranges::empty_view ranges::single_view ranges::iota_view ranges::basic_istream_view ranges::repeat_view ranges::cartesian_product_view views::all_t ranges::ref_view ranges::owning_view ranges::lazy_split_view views::counted ranges::common_view ranges::reverse_view ranges::as_const_view ranges::as_rvalue_view
aims at order-of/modifying/reordering elements (checks physical storage style/changes physical storage style/changes sequential relationships between elements, for future use) instead of calculating a result, so not relevant copy move fill remove replace swap reverse rotate shift_left shift_right unique partition stable_partition sort partial_sort stable_sort merge inplace_merge is_heap is_heap_until is_permutation next_permutation prev_permutation
calculated result can not be reused and must be recalculated every time, so not relevant shuffle sample
requires domain-specific algorithm, generality is sacrificed, so not relevant search
requires multiple sequences, so not relevant mismatch find_end starts_with ends_with includes set_difference set_intersection set_symmetric_difference set_union equal lexicographical_compare lexicographical_compare_three_way inner_product ranges::zip_view ranges::zip_transform_view

Function Members

Constructors, Assignments, Swap and Destructor

(To scroll horizontally, press and hold down the shift key and scroll the mouse.)

Actions Parameters Complexity Exceptions Notes
empty
augmented_deque_t();
p = create_and_link_end_nodes()
O(1) (todo)
explicit augmented_deque_t(
	allocator_element_t const &allocator_element);
(todo)
void clear() &;
pop_back() until empty()
O(N) (todo)
count default-inserted elements
explicit augmented_deque_t(
	size_type count,
	allocator_element_t const &allocator_element = allocator_element_t());
p = create_and_link_end_nodes()
emplace_back() count elements
O(count) (todo)
count copy-inserted elements
explicit augmented_deque_t(
	size_type count,
	element_t const &value,
	allocator_element_t const &allocator_element = allocator_element_t());
(todo)
void assign(
	size_type count,
	element_t const &value) &;
pop_back() until empty()
emplace_back() count elements
O(N+count) (todo)
comparable range
template<
	std::input_iterator iterator_t,
	std::sentinel_for<iterator_t> sentinel_t>
augmented_deque_t(
	iterator_t iterator,
	sentinel_t sentinel,
	allocator_element_t const &allocator_element = allocator_element_t());
p = create_and_link_end_nodes()
emplace_back() range's elements
O(distance(subrange(iterator,sentinel))) (todo)
template<
	std::input_iterator iterator_t,
	std::sentinel_for<iterator_t> sentinel_t>
void assign(
	iterator_t iterator,
	sentinel_t sentinel) &;
pop_back() until empty()
emplace_back() range's elements
O(N+distance(subrange(iterator,sentinel))) (todo)
std::initializer_list
augmented_deque_t(
	std::initializer_list<element_t> initializer_list,
	allocator_element_t const &allocator_element = allocator_element_t());
p = create_and_link_end_nodes()
emplace_back() initializer_list's elements
O(distance(initializer_list)) (todo)
augmented_deque_t &operator=(
	std::initializer_list<element_t> initializer_list) &;
pop_back() until empty()
emplace_back() initializer_list's elements
O(N+distance(initializer_list)) (todo)
void assign(
	std::initializer_list<element_t> initializer_list) &;
(todo)
Actions Parameters Complexity Exceptions Notes
copy
augmented_deque_t(
	augmented_deque_t const &other);
p = create_and_link_end_nodes()
emplace_back() other's elements
O(distance(other)) (todo)
augmented_deque_t(
	augmented_deque_t const &other,
	std::type_identity_t<allocator_element_t> const &allocator_element);
(todo)
augmented_deque_t &operator=(
	augmented_deque_t const &other) &;
pop_back() until empty()
propagate_on_container_copy_assignment
false true
this->allocator_element and other.allocator_element == / /
!= /
destroy_end_nodes(p)
this->allocator_element = other.allocator_element
p = create_and_link_end_nodes()
emplace_back() other's elements
O(N+distance(other)) (todo)
move
augmented_deque_t(
	augmented_deque_t &&other);
this->p = other.p
other.p = create_and_link_end_nodes()
(: allocator_element(move(other.allocator_element)) happens at the end)
O(1) (todo)
augmented_deque_t(
	augmented_deque_t &&other,
	std::type_identity_t<allocator_element_t> const &allocator_element);
allocator_element and other.allocator_element ==
this->p = other.p
other.p = create_and_link_end_nodes()
!=
this->p = create_and_link_end_nodes()
emplace_back(move()) other's elements
(other.size() is not changed)
allocator_element and other.allocator_element == O(1)
!= O(distance(other))
(todo)
augmented_deque_t &operator=(
	augmented_deque_t &&other) &;
pop_back() until empty()
propagate_on_container_move_assignment
false true
this->allocator_element and other.allocator_element ==
swap(this->p, other.p)
!=
emplace_back(move()) other's elements
(other.size() is not changed)
destroy_end_nodes(p)
this->allocator_element = move(other.allocator_element)
p = create_and_link_end_nodes()
swap(this->p, other.p)
propagate_on_container_move_assignment
false true
this->allocator_element and other.allocator_element == O(N)
!= O(N+distance(other)) O(N)
(todo)
swap
void swap(
	augmented_deque_t &other);
propagate_on_container_swap
false true
this->allocator_element and other.allocator_element ==
swap(this->p, other.p)
!=
augmented_deque_t temp_this(other, this->allocator_element)
augmented_deque_t temp_other(*this, other.allocator_element)
swap(this->p, temp_this.p)
swap(other.p, temp_other.p)
swap(this->allocator_element, other.allocator_element)
swap(this->p, other.p)
propagate_on_container_swap
false true
this->allocator_element and other.allocator_element == O(1)
!= O(N+distance(other)) O(1)
(todo)
destructor
~augmented_deque_t();
pop_back() until empty()
destroy_end_nodes(p)
O(N) (todo)